class Solution {
public:
    bool check(const string& s1,const string& s2){
        if(s1.size() == s2.size()){
            return s1 < s2;
        }
        return s1.size() < s2.size();
    }   
                                        
    string largestNumber(vector<int>& cost, int target) {    
        int n = cost.size();
        vector<string> dp(target+1,"-1");
        dp[0] = "";
        
        for(int i = 0;i < n;i++){
            for(int j = 1;j <= target;j++){
                if(j >= cost[i] && dp[j-cost[i]] != "-1"){
                    if(dp[j] == "-1"){
                        dp[j] = to_string(i+1) + dp[j-cost[i]];
                    }
                    else if(check(dp[j],to_string(i+1) + dp[j-cost[i]])){
                         dp[j] = to_string(i+1) + dp[j-cost[i]];
                    }
                }
            }
        }
        if(dp[target] == "-1") return "0";
                        
        return dp[target];               
    }
};
